package com.hardy.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * User: Ruijie Date: 2016/8/24
 */
public class Triangle {

    public static int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if(triangle.size()==1){
            Integer result=triangle.get(0).get(0);
            System.out.println(result+"-------");
            return triangle.get(0).get(0);
        }
        int n = triangle.size();
        int[] below = new int[n];
        int[] cur = new int[n];
        List<Integer> last=triangle.get(n-1);
        for(int i=0;i<last.size();i++){
            below[i]=last.get(i);
        }
        for(int i=n-2;i>=0;i--){
            List<Integer> curList=triangle.get(i);
            for(int j=0;j<curList.size();j++){
                if(below[j]>below[j+1]){
                    cur[j]=below[j+1]+curList.get(j);
                }else{
                    cur[j]=below[j]+curList.get(j);
                }
            }
            //更新底部
            for(int k=0;k<n;k++){
                below[k]=cur[k];
            }
        }
        return cur[0];
    }

    public static void main(String[] args) {
        ArrayList temp=new ArrayList();
        ArrayList array=new ArrayList();
        array.add(-10);
        temp.add(array);
      /*  temp.add(Arrays.asList(3,4));
        temp.add(Arrays.asList(6,5,7));
        temp.add(Arrays.asList(4,1,8,3));*/
        System.out.println(minimumTotal(temp));
    }
}
